package algorithm.FindMinPath;

import java.util.*;

/*
给定两个字符串，记为start和to，再给定一个字符串列表list，list中一定包含to（且list中没有重复字符串），所有的字符串都是小写
规定：start每次只能改变一个字符，最终的目标是变成to，但是每次变成的新字符串必须在list中存在
请返回所有最短的变换路径

例：
start="abc",to="cab",list={"cab","acc","cbc","ccc","cac","cbb","aab","abb"}
 */
public class FindMinPath {

    public static List<List<String>> getResList(String start, String to, List<String> list) {
        HashMap<String, List<String>> path = drawPath(start, list);
        System.out.println(path);

        HashMap<String, Integer> pathLength = new HashMap<>();
        pathLength.put(start, 0);
        getPathLength(start, path, pathLength);

        List<List<String>> resList = new LinkedList<>();
        LinkedList<String> pathList = new LinkedList<>();
        through(start, to, path, pathLength, pathList, resList);
        return resList;
    }

    //start到每个String的距离
    private static void getPathLength(String start,
                                      HashMap<String, List<String>> path,
                                      HashMap<String, Integer> pathLength) {
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        HashSet<String> set = new HashSet<>();
        set.add(start);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String next: path.get(cur)) {
                if (!set.contains(next)) {
                    pathLength.put(next, pathLength.get(cur) + 1);
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }

    //每个String的邻居
    public static HashMap<String, List<String>> drawPath(String start, List<String> list) {
        HashMap<String, List<String>> pathMap = new HashMap<>();
        list.add(start);
        HashSet<String> set = new HashSet<>(list);

        for (int i = 0; i < list.size(); i++) {
            String cur = list.get(i);
            LinkedList<String> neibs = new LinkedList<>();
            char[] str = cur.toCharArray();
            for (int j = 0; j < str.length; j++) {      // M
                char tmp = str[j];
                for (char k = 'a'; k <= 'z'; k++) {
                    str[j] = k;
                    String s = String.valueOf(str);
                    if (!s.equals(cur) && set.contains(s)) {
                        neibs.add(s);
                     }
                }
                str[j] = tmp;
            }

            pathMap.put(cur, neibs);
        }
        return pathMap;
    }

    public static void through(String cur, String to,
                                             HashMap<String, List<String>> pathMap,
                                             HashMap<String, Integer> pathLength,
                                             LinkedList<String> curList,
                                             List<List<String>> resList) {

        curList.add(cur);
        if (cur.equals(to))
            resList.add(new LinkedList<>(curList));
        else
            for (String next: pathMap.get(cur)) {
                if (pathLength.get(next) == pathLength.get(cur) + 1) {
                    through(next, to, pathMap, pathLength, curList, resList);
                }
            }
        curList.pollLast();
    }

    public static void main(String[] args) {
        String start="abc", to="cab";
        List list = new ArrayList<String>(Arrays.asList(new String[]{"cab", "acc", "cbc", "ccc", "cac", "cbb", "aab", "abb"}));
        System.out.println(getResList(start, to, list));
    }
}
